import javax.swing.plaf.basic.BasicInternalFrameTitlePane;
import java.time.Period;
import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-06-20
 * Time: 23:29
 */

class Tire{
    public Tire[] arr = new Tire[27];
}

public class Solution {
    int count; // 记录已经存储了几个字符串了
    Tire root;
    public Solution() {
        this.root = new Tire();
    }

    /**
     *  创建字典树
     * @param str
     */
    public void createTire(String str){
        Tire cur = this.root;
        for (char c: str.toCharArray()) {
            if (cur.arr[c-'a'] == null) {
                cur.arr[c-'a'] = new Tire();
            }
            cur = cur.arr[c-'a'];
        }
        cur.arr[26] = new Tire();
    }


    public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        List<List<String>> ans = new ArrayList<>();
        int len = searchWord.length();
        for (int i = 0; i < len; i++) {
            List<String> list = new ArrayList<>();
            ans.add(list);
        }
        // 先创建出树
        for (String s: products) {
            createTire(s);
        }
        // 将每个前缀都进行匹配
        for (int i = 0; i < len; i++) {
            // 每次匹配前都要置为 0
            count = 0;
            search(searchWord.substring(0, i+1), ans.get(i));
        }
        return ans;
    }

    /**
     *  根据 substring 进行匹配, 并将结果存入 list  中
     * @param substring
     * @param list
     */
    private void search(String substring, List<String> list) {
        Tire cur = root;
        // 先看看能不能匹配
        for (char c: substring.toCharArray()) {
            if (cur.arr[c-'a'] == null) {
                // 说明根本匹配不到
                return;
            }
            // 不要忘记移动 cur
            cur = cur.arr[c-'a'];
        }
        // 说明能匹配到
        StringBuilder stringBuilder = new StringBuilder(substring);
        // 匹配到了, 需要返回前三个
        preorder(cur, stringBuilder, list);
    }

    private void preorder(Tire cur, StringBuilder stringBuilder, List<String> list) {
        if (cur == null || count == 3) {
            // 如果匹配到最后或者 已经记录三个了, 那么直接返回
            return;
        }
        // 当前就能匹配到
        if (cur.arr[26] != null) {
            list.add(stringBuilder.toString());
            count++;
        }
        // 继续添加比当前更长的字符串
        for (int i = 0; i < 26; i++) {
            if (cur.arr[i] != null) {
                stringBuilder.append((char)('a'+i));
                preorder(cur.arr[i], stringBuilder, list);
                // 不要忘记回溯时删除最后一个字母
                stringBuilder.deleteCharAt(stringBuilder.length()-1);
            }
        }
    }
}


class Trie{
    Trie [] arr;
    // 用大堆记录以某个前缀开始的最小的三个字符串
    PriorityQueue<String> maxHeap;
    public Trie(){
        this.arr = new Trie[27];
        maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
    }
}

class Solution2{
    Trie root = new Trie();
    /**
     *  创建字典树
     * @param str
     */
    public void createTire(String str){
        Trie cur = this.root;
        for (char c: str.toCharArray()) {
            if (cur.arr[c-'a'] == null) {
                cur.arr[c-'a'] = new Trie();
            }
            // 每个节点记录三个以该字符串为前缀的最小的三个字符串
            if (cur.maxHeap.size() < 3 || (cur.maxHeap.peek().compareTo(str)) > 0) {
                if (cur.maxHeap.size() == 3) {
                    cur.maxHeap.poll();
                }
                cur.maxHeap.offer(str);
            }
            cur = cur.arr[c-'a'];
        }
        cur.arr[26] = new Trie();
        // 最后一个也要记录, 最后一个不用跟其他的比较, 因为它与前缀一摸一样, 所以直接就是最短的
        if (cur.maxHeap.size() == 3) {
            cur.maxHeap.poll();
        }
        cur.maxHeap.offer(str);
    }


    public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        List<List<String>> ans = new ArrayList<>();
        int len = searchWord.length();
        for (int i = 0; i < len; i++) {
            List<String> list = new ArrayList<>();
            ans.add(list);
        }
        // 先创建出树
        for (String s: products) {
            createTire(s);
        }
        // 将每个前缀都进行匹配
        for (int i = 0; i < len; i++) {
            search(searchWord.substring(0, i+1), ans.get(i));
        }
        return ans;
    }


    private void search(String substring, List<String> list) {
        Trie cur = root;
        // 先看看能不能匹配
        for (char c: substring.toCharArray()) {
            if (cur.arr[c-'a'] == null) {
                // 说明根本匹配不到
                return;
            }
            // 不要忘记移动 cur
            cur = cur.arr[c-'a'];
        }
        // 匹配到了, 需要返回前三个
        PriorityQueue<String> minHeap = new PriorityQueue<>(Comparator.naturalOrder());
        // 注意要从小往大加, 所以要大堆换为小堆
        minHeap.addAll(cur.maxHeap);
        int size = minHeap.size();
        for (int i = 0; i < size; i++) {
            list.add(minHeap.poll());
        }
    }
}

class Solution3{
    public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        List<List<String>> ans = new ArrayList<>();
        Arrays.sort(products);
        int alen = products.length;
        int len = searchWord.length();
        for (int i = 0; i < len; i++) {
            List<String> list = new ArrayList<>();
            ans.add(list);
        }
        // 因为前缀的顺序是越来越大的, 所以二分查找的左边起始位置可以设置为上一个前缀找到的位置
        int position = 0;
        // 将每个前缀都进行匹配
        for (int i = 0; i < len; i++) {
            String prefix = searchWord.substring(0, i+1);
            // 进行二分查找
            int left = position;
            int right = alen-1;
            // 找最小的 以 prefix 为前缀的字符串
            while (left < right) {
                int mid = ((right-left) >> 1) + left;
                if (products[mid].compareTo(prefix) < 0) {
                    left = mid + 1;
                }else {
                    right = mid;
                }
            }
            // 更新 position, 降低了一部分时间复杂度
            position = left;
            // 找最小的三个, 但是不能越界
            for (int j = 0; j < 3 && (left + j) < alen; j++) {
                if (products[left+j].startsWith(prefix)) {
                    ans.get(i).add(products[left+j]);
                }
            }
        }
        return ans;
    }
}
